﻿/*
A KMP模式匹配算法
分数 15
作者 朱允刚
单位 吉林大学
给定主串s和模式串p，编写程序使用KMP算法进行模式匹配，计算p在s中出现的首位置，若p不在s中则输出−1。字符串下标从0开始。

输入格式:
输入为2行，第1行为主串s，第2行为模式串p。主串和模式串长度不超过105。

输出格式:
输出为2行，第1行为3个整数，表示分别在模式串p的pm/4 ,p2m/4 ,p3m/4处失配后，模式串下一次匹配的位置（即next[j]或f[j−1]+1的值，j=m/4,2m/4,3m/4），每个整数后一个空格，m表示模式串p的长度；第2行为一个整数，表示p在s中出现的首位置，若p不在s中则输出−1。

输入样例:
qwerababcabcabcabcdaabcabhlk
abcabcabcabc

输出样例:
0 3 6
6
代码长度限制
16 KB
时间限制
20 ms
内存限制
10 MB
*/

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{

    string s, p;
    cin >> s >> p;

    int m = s.length(); // main
    int n = p.length(); // vice

    // get NEXT vec;
    vector<int> next(n, 0);
    int j = 0;
    for (int i = 1; i < n; i++)
    {
        while (j > 0 && p[j] != p[i])
            j = next[j - 1];
        if (p[i] == p[j])
            j++;
        next[i] = j;
    }

    // KMP;
    int index = -1;
    j = 0;
    for (int i = 0; i < m; i++)
    {
        while (j > 0 && s[i] != p[j])
            j = next[j - 1];
        if (s[i] == p[j])
            j++;
        if (j == n) {
            index = i - n + 1;
            break;
        }
    }

    cout << next[n / 4]-1 << " " << next[2 * n / 4]-1 << " " << next[3 * n / 4]-1 << endl;
	cout << index << endl;
	return 0;
}

/*
#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 计算模式串p的next数组
vector<int> computeNext(const string& p) {
    int m = p.length();
    vector<int> next(m, 0);

    for (int i = 1, j = 0; i < m; ++i) {
        while (j > 0 && p[i] != p[j]) {
            j = next[j - 1];
        }
        if (p[i] == p[j]) {
            j++;
        }
        next[i] = j;
    }

    return next;
}

// 使用KMP算法进行模式匹配
int kmp(const string& s, const string& p) {
    int n = s.length();
    int m = p.length();

    vector<int> next = computeNext(p);

    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && s[i] != p[j]) {
            j = next[j - 1];
        }
        if (s[i] == p[j]) {
            j++;
        }
        if (j == m) {
            return i - m + 1;
        }
    }

    return -1;
}

int main() {
    string s, p;
    getline(cin, s);
    getline(cin, p);

    int m = p.length();

    vector<int> next = computeNext(p);

    cout << next[m / 4] << " " << next[2 * m / 4] << " " << next[3 * m / 4] << endl;

    int result = kmp(s, p);
    cout << result << endl;

    return 0;
}
*/
